import java.util.ArrayList;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 08 - 22
 * Time: 20:23
 */
//牛客 合并k个已排序的链表
class Solution6 {
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        return merge1(lists, 0, lists.size() - 1);
    }
    public ListNode merge1(ArrayList<ListNode> lists, int left, int right) {
        if(left > right) return null;//left>right和left==right要分开两种情况返回
        if(left == right) return lists.get(left);
        int mid = (left + right) / 2;
        ListNode list1 = merge1(lists, left, mid);
        ListNode list2 = merge1(lists, mid + 1, right);
        return Merge (list1, list2);
    }
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        ListNode node = new ListNode(-1);
        ListNode cur = node;
        while (pHead1 != null && pHead2 != null) {
            if (pHead1.val < pHead2.val) {
                cur.next = pHead1;
                cur = cur.next;
                pHead1 = pHead1.next;
            } else {
                cur.next = pHead2;
                cur = cur.next;
                pHead2 = pHead2.next;
            }
        }
        while (pHead1 != null) {
            cur.next = pHead1;
            break;
        }
        while (pHead2 != null) {
            cur.next = pHead2;
            break;
        }
        return node.next;
    }
}
